class Solution {
    public boolean findSort(int i, int end, int target){
        if(i > end)//判断i是不是在前一段有序数组中
            return target > end && i >= target;
        else//后一段
            return target > end || i >= target;
    }
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int end = nums[right];
        while(left <= right){
            int mid = left + (right - left)/2;
            if(findSort(nums[mid],end,target)){
                right = mid-1;
            }else{
                left = mid+1;
            }
        }
        if(right+1 == nums.length || nums[right+1] != target){
            return -1;
        }
        return right+1;
    }
}
class Solution {
    public int search(int[] nums, int target) {
        if(nums[0] == target) return 0;
        int l = 0;
        int r = nums.length-1;
        int ans = -2;
        while(l<=r){
            int mid=l+(r-l)/2;//[l,r]
            if(nums[mid]>nums[nums.length-1]){
                l=mid+1;//[mid+1,r];
            }else{
                r=mid-1;
            }
        }//r+1
        if(nums[nums.length-1]>target){
            ans = search_target(nums,target,r+1,nums.length-1);
        }else if(nums[nums.length-1]<target){
            ans = search_target(nums,target,0,r+1);
        }else{
            return nums.length - 1;
        }
        return ans;
    }
    public int search_target(int[] nums,int target,int l,int r){
        while(l<=r){
            int mid = l + (r-l)/2;//[l,r]
            if(nums[mid]>target){
                r=mid-1;
            }else if(nums[mid]<target){
                l=mid+1;
            }else{
                return mid;
            }
        }
        return -1;
    }
}
class Solution {
    public ListNode reserve(ListNode head){
        ListNode prev = null;
        ListNode cur = head;
        while(cur != null){
            ListNode curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        return prev;
    }
    public ListNode addTwo(ListNode l1, ListNode l2) {
        ListNode head = new ListNode();
        ListNode nhead = head;
        int tmp = 0;
        while(l1 != null || l2 != null || tmp != 0){
            if(l1 != null) tmp += l1.val;
            if(l2 != null) tmp += l2.val;
            nhead = nhead.next = new ListNode(tmp%10);
            tmp /= 10;
            if(l1 != null)l1 = l1.next;
            if(l2 != null)l2 = l2.next;
        }
        return head.next;
    }
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        l1 = reserve(l1);
        l2 = reserve(l2);
        ListNode l3 = addTwo(l1,l2);
        return reserve(l3);
    }
}

public class Test {
}
